Forest Fire
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You're given a grid representing a plot of forest. Each cell holds one of three values: bare ground, a healthy tree, or a tree that's already on fire.
Every minute, fire spreads from each burning tree to its healthy up/down/left/right neighbors, turning them into burning trees for the next minute. Return the number of minutes until no healthy tree is left, or -1 if some healthy tree can never catch fire.
Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
Output: 4
The fire spreads outward one ring per minute from the burning tree at the top-left. The bare cell in the middle row never catches anything, since it isn't a tree. The last healthy tree catches fire on minute 4.
Input: grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]
Output: -1
The tree in the bottom-left corner is surrounded by bare ground, so it can never catch fire no matter how long we wait.
Input: grid = [[2, 2], [2, 2]]
Output: 0
Every tree is already burning, so 0 minutes pass.
You might also hear this problem called “Rotting Oranges.”
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.